using System;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0486. 预测赢家")]
    public class No0486_PredictTheWinner : AbsBaseTestItem
    {
        /*
        给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。
        给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。
        提示：
            1 <= 给定的数组长度 <= 20.
            数组里所有分数都为非负数且不会大于 10000000 。
            如果最终两个玩家的分数相等，那么玩家 1 仍为赢家。
        */

        public override void OnTest()
        {
            Assert.TestExe(PredictTheWinner, new int[] { 1, 5, 2 }, false);
            Assert.TestExe(PredictTheWinner, new int[] { 1, 5, 233, 7 }, true);

            Assert.TestExe(PredictTheWinner_2, new int[] { 1, 5, 2 }, false);
            Assert.TestExe(PredictTheWinner_2, new int[] { 1, 5, 233, 7 }, true);
        }

        /// <summary>
        /// 方法一：递归
        /// </summary>
        public bool PredictTheWinner(int[] nums)
        {
            int total(int[] nums, int start, int end, int turn)
            {
                if (start == end)
                {
                    return nums[start] * turn;
                }
                int scoreStart = nums[start] * turn + total(nums, start + 1, end, -turn);
                int scoreEnd = nums[end] * turn + total(nums, start, end - 1, -turn);
                return Math.Max(scoreStart * turn, scoreEnd * turn) * turn;
            }
            return total(nums, 0, nums.Length - 1, 1) >= 0;
        }

        /// <summary>
        /// 方法二：动态规划
        /// </summary>
        public bool PredictTheWinner_2(int[] nums)
        {
            int n = nums.Length;
            int[] dp = new int[n];
            for (int i = 0; i < n; i++)
            {
                dp[i] = nums[i];
            }
            for (int i = n - 2; i >= 0; i--)
            {
                for (int j = i + 1; j < n; j++)
                {
                    dp[j] = Math.Max(nums[i] - dp[j], nums[j] - dp[j - 1]);
                }
            }
            return dp[n - 1] >= 0;
        }
    }
}
